package com.winsomely.leecode;

import com.winsomely.leecode.model.ListNode;

/**
 * 相交链表
 * 
 * @author liujiawei
 *
 */
public class GetIntersectionNode {

	/**
	 * 4,1,8,4,5 5,6,1,8,4,5
	 * 
	 * @param headA
	 * @param headB
	 * @return
	 */
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		ListNode nextA = headA;
		ListNode nextB = headB;
		boolean linkA = false;
		boolean linkB = false;

		while (nextA != null && nextB != null) {
			if (nextA == nextB) {
				return nextA;
			}
			ListNode tempA = nextA.next;
			ListNode tempB = nextB.next;

			if (tempA != null) {
				nextA = tempA;
			} else if (!linkA) {
				nextA = headB;
				linkA = true;
			} else {
				nextA = null;
			}

			if (tempB != null) {
				nextB = tempB;
			} else if (!linkB) {
				nextB = headA;
				linkB = true;
			} else {
				nextB = null;
			}
		}
		return null;
	}

	public static void main(String[] args) {

	}

}
